206. ট্যুরিস্ট

গেনা তার স্কুল ট্যুরে যাচ্ছে। সে তার ক্লাসের তাঁবু সরবরাহের দায়িত্ব নিয়েছে। বাড়িতে গিয়ে ও ৩টা তাঁবু পেল: প্রথমটার ওজন a₁ কেজি এবং সেটাতে b₁ জন থাকতে পারে, দ্বিতীয়টা a₂ কেজি আর তাতে b₂ জন থাকতে পারে, তৃতীয়টা a₃ কেজি আর তাতে থাকতে পারে b₃ জন।

গেনার ক্লাসে k জন ছাত্র আছে। গেনা কি এমনভাবে তাঁবু বাছাই করতে পারবে যাতে করে সবার জায়গা হয়ে যায়? লক্ষ্য রেখ, বাছাই করা তাঁবুর ওজন যেন w কেজির বেশি না হয়।

ইনপুটঃ

প্রথম লাইনে থাকবে দুটো সংখ্যা k আর w (1 ≤ k ≤ 15, 1 ≤ w ≤ 30). এর পরের লাইনে থাকবে ছটা সংখ্যা: a₁, b₁, a₂, b₂, a₃, b₃ (1 ≤ a₁, a₂, a₃ ≤ 10, 1 ≤ b₁, b₂, b₃ ≤ 15).

আউটপুটঃ

যদি বাছাই করা যায় তবে YES প্রিন্ট কর। আর না গেলে NO।

উদাহরণ

ইনপুট

10 10

5 5 6 6 4 5

আউটপুট

YES

সমাধান

প্রাথমিক সমস্যা – কন্ডিশনাল স্টেটমেন্ট

অ্যালগোরিদম অ্যানালাইসিস

যেহেতু তাঁবু মাত্র তিনটা, আমরা ছাত্রদের সব উপায়ে তাঁবুগুলোতে রেখে দেখবো। দেখি আমরা ছাত্রদের কোন কোন ভাবে রাখতে পারি

· শুধু প্রথম তাঁবুতে;

· শুধু দ্বিতীয় তাঁবুতে;

· শুধু তৃতীয় তাঁবুতে;

· প্রথম আর দ্বিতীয় তাঁবুতে;

· প্রথম আর তৃতীয় তাঁবুতে;

· দ্বিতীয় আর তৃতীয় তাঁবুতে;

· সবগুলো তাঁবুতেই।

এই উপায়গুলোকে আমরা সাতটা কন্ডিশনাল স্টেটমেন্টের সাহায্যে লিখতে পারি। flag নামে একটা ভ্যারিয়েবল ডিক্লেয়ার করি, শুরুতে এটার মান 0 রাখি (শুণ্য মানে সব ছাত্রকে তাঁবুতে রাখা যাবে না, এক মানে বসানো যাবে – পরে আমরা দেখবো)। এরপর সাতটা সম্ভাব্য উপায় চেক করে দেখি।

উদাহরণস্বরূপঃ শুধু প্রথম আর দ্বিতীয় তাঁবুতে রাখার শর্ত হচ্ছে:

if ((b2 >= k) && (a2 <= w)) flag = 1;

আবার, শুধু প্রথম আর তৃতীয় তাঁবুতে রাখার শর্ত হচ্ছে:

if ((b1 + b3 >= k) && (a1 + a3 <= w)) flag = 1;

সাতটা জিনিস চেক করার পরে flag এর মান দেখে আমরা উত্তর প্রিন্ট করবো।

অ্যালগোরিদম বাস্তবায়ন

সম্ভাব্য সব উপায়ে ছাত্রদের তাঁবুতে রেখে।

scanf("%d %d",&k,&w);

scanf("%d %d %d %d %d %d",&a1,&b1,&a2,&b2,&a3,&b3);

if ((b1 >= k) && (a1 <= w)) flag = 1;

if ((b2 >= k) && (a2 <= w)) flag = 1;

if ((b3 >= k) && (a3 <= w)) flag = 1;

if ((b1 + b2 >= k) && (a1 + a2 <= w)) flag = 1;

if ((b1 + b3 >= k) && (a1 + a3 <= w)) flag = 1;

if ((b2 + b3 >= k) && (a2 + a3 <= w)) flag = 1;

if ((b1 + b2 + b3 >= k) && (a1 + a2 + a3 <= w)) flag = 1;

if (flag) printf("YES\n"); else printf("NO\n");